/*******************************************

  TRABALHO DE CONCORRENTES - PROJETO 2

  Hospital ICMCTown

********************************************/

/*********************
Bibliotecas
*********************/
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>

/*********************
Definições
*********************/
#define MASTER      0          /* taskid of first task */
#define FROM_MASTER 1          /* setting a message type */
#define FROM_WORKER 2          /* setting a message type */

#define INFINITE    1000000000

/*********************
Funções gerais
*********************/

//  int readNumJuncoes()
//  le o numero de Juncoes
  int readNumJuncoes()
  {
    int numJuncoes;

    scanf("%d", &numJuncoes);
    if( !((numJuncoes >= 2) && (numJuncoes <= 1000)) )
    {
      printf("-----------\nNumero de Juncoes nao esta no intervalo especificado.\n-----------\n\n");
      abort();
    }

    return numJuncoes;
  }

//  int readNumLinhas(int numJuncoes)
//  Le o numero de Linhas
  int readNumLinhas(int numJuncoes)
  {
    int numLinhas;

    scanf("%d", &numLinhas);
    if( !((numLinhas >= (numJuncoes-1)) && ( numLinhas <= ((numJuncoes*(numJuncoes-1))/2))) )
    {
      printf("-----------\nNumero de Linhas nao esta no intervalo especificado.\n-----------\n\n");
      abort();
    }

    return numLinhas;
  }



//  void defineJuncoes(int *a, int *b, int i, int numJuncoes)
//  coloca as informacoes das juncoes nos vetores
  void defineJuncoes(int *a, int *b, int i, int numJuncoes)
  {
    scanf("%d", &a[i]);
    if( !(a[i] >= 1 && a[i] <= numJuncoes) ) printf("-----------\nJuncao nao esta existe.\n-----------\n\n"), abort();
    
    scanf("%d", &b[i]);
    if( !(b[i] >= 1 && b[i] <= numJuncoes) ) printf("-----------\nJuncao nao esta existe.\n-----------\n\n"), abort();
    if( a[i] == b[i] ) printf("-----------\nJuncoes iguais.\n-----------\n\n"), abort();
  }

//  void distanciaJuncoes(int *w, int i)
//  coloca as informacoes das juncoes nos vetores
  void distanciaJuncoes(int *w, int i)
  {
    scanf("%d", &w[i]);
    if( !(w[i] >= 1 && w[i] <= 100000) ) printf("-----------\nTamanho do caminho nao esta no intervalo especificado.\n-----------\n\n"), abort();
  }

// void montarGrafo(int *a, int *b, int *w, int numJuncoes, int numLinhas, int **grafo)
// Monta o grafo das distancias, sendo linha referente a juncao inicial, coluna a final e o valor a distancia
  void montarGrafo(int *a, int *b, int *w, int numJuncoes, int numLinhas, int **grafo)
  {
    int i, j;

    for(i=0;i<numLinhas;i++)
    {
      grafo[a[i]-1][b[i]-1] = w[i];
      grafo[b[i]-1][a[i]-1] = w[i];
    }
  }

// int minDistance(int dist[], int numJuncoes, bool sptSet[])
// Acha a distancia vertice com a menor distancia
  int minDistance(int *dist, int numJuncoes, bool *sptSet)
  {
   int min = INT_MAX, min_index;
   int v;
   for (v = 0; v < numJuncoes; v++)
     if (sptSet[v] == false && dist[v] <= min)
       min = dist[v], min_index = v;

     return min_index;
   }

// int maximo(int *dist int numJuncoes)
// Acha a maior distancia do conjunto do vetor de distancias
  int maximo(int *dist, int numJuncoes)
  {
   int i, aux=0;
   for (i = 0; i < numJuncoes; i++)
    if(dist[i] > aux) aux = dist[i];
  return aux;
  }

// int dijkstra(int **graph, int numJuncoes, int src)
// Implementa o algoritmo de Dijkstra
  int dijkstra(int **graph, int numJuncoes, int src)
  {
     int i, count,v;
     int dist[numJuncoes];     // O vetor de distrancias.
                               // dist[i] terá a menor distância da raiz até i

     bool sptSet[numJuncoes];  // sptSet[i] irá definir como verdadeiro se o vértice i estiver incluso na
                               // arvore de menor caminho ou menor distância da raiz até o vértice estiver
                               // finalizada

     // Inicializa todas as distâncias em infinito e os caminhos como falsos(não acessados)
     for (i = 0; i < numJuncoes; i++)
      dist[i] = INT_MAX, sptSet[i] = false;

     // Distância do vértice raiz a ele mesmo é zero (Sempreee!)
     dist[src] = 0;

     // Encontra o menor caminho para todos os vértices
    for (count = 0; count < numJuncoes-1; count++)
    {
      // Pega a menor distância do conjunto de vértices ainda não processado 
      int u = minDistance(dist, numJuncoes, sptSet);

      // Marca o vértice como processado
      sptSet[u] = true;

      // Atualiza o valor da distância dos vértices adjacentes ao vértice pego
      for (v = 0; v < numJuncoes; v++)

       // Atualiza dist[v] somente se não estiver em sptSet, onde houver uma conexão de
       // u até v, e o peso total do caminho da raiz até v através de u for menor do que
       // o atual valor da distância de dist[v]
       if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
         && dist[u]+graph[u][v] < dist[v])
          dist[v] = dist[u] + graph[u][v];
    }

    // retorna o valor maximo de todas as distancias encontradas
    return maximo(dist,numJuncoes);
  }



/******************
Função Principal
*******************/
int main()
{
    int numLinhas, numJuncoes;
    int *a,*b,*w;     // a[] e b[]  numero das juncoes
                      // w[]        distancia das juncoes
    int *min;
    int aux=INFINITE;

    int i;            // contador
    int j;

    int **grafo;

    // Entrada de Dados
    numJuncoes = readNumJuncoes();
    numLinhas = readNumLinhas(numJuncoes);

    // Alocação de variaveis
    a = (int *) calloc(numLinhas,sizeof(int));
    b = (int *) calloc(numLinhas,sizeof(int));
    w = (int *) calloc(numLinhas,sizeof(int));
    min = (int *) calloc(numJuncoes,sizeof(int));

    // Entrada de Dados
    for(i=0;i<numLinhas; i++)
    {
      defineJuncoes(a,b,i,numJuncoes);
      distanciaJuncoes(w,i);
    }

    grafo = (int **) calloc(numJuncoes,sizeof(int *));
    for(i=0;i<numJuncoes+1;i++) grafo[i] = (int *) calloc(numJuncoes,sizeof(int));

    montarGrafo(a,b,w,numJuncoes,numLinhas,grafo);

    // Efetivamente aqui ocorre a realização do programa
    // E execução do algoritmo
    for(i=0;i<numJuncoes;i++) min[i] = dijkstra(grafo, numJuncoes, i); // todos os valores maiores
    for(i=0;i<numJuncoes;i++) if(min[i] < aux) aux = min[i];

    // Imprime resultado final
    printf("%d\n", aux);

    // Libera informações
    free(a);
    free(b);
    free(w);
    free(min);
    for(i=0;i<numJuncoes+1;i++) free(grafo[i]);
    free(grafo);

    return 0;
  }